package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 希尔排序 - 缩小增量排序（时间复杂度 O(nlog2n)）
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
		System.out.println("排序前：" + Arrays.toString(arr));
		shellSort1(arr);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
		int[] arrBatch = new int[100000];
		for (int i = 0; i < 100000; i++) {
			arrBatch[i] = (int) (Math.random() * 100000);
		}
		long begin = System.currentTimeMillis();
		shellSort(arrBatch);
		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	/**
	 * 希尔排序 - 交换法
	 */
	public static void shellSort(int[] arr) {
		int temp;
		// 分组次数，每次按照 gap 来分
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			// 遍历 gap 中的元素（gap 为起点，后边的元素依次和 该元素前边的同组元素比较【此处采用交换】）
			for (int i = gap; i < arr.length; i++) {
				for (int j = i - gap; j >= 0; j -= gap) {
					if (arr[j] > arr[j + gap]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
		}
	}

	/**
	 * 希尔排序 - 移位法
	 */
	public static void shellSort1(int[] arr) {
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				int temp = arr[j];
				// 如果同组后边的比前边得小，需要依次和同组前边的成员比较
				if (arr[j] < arr[j - gap]) {
					// 如果比前边的成员小，则 把前边成员的值 付给当前，temp 存储当前的值（即最小的值）
					while (j - gap >= 0 && temp < arr[j - gap]) {
						arr[j] = arr[j - gap];
						j -= gap;
					}
					// 最后退出把 temp（最小的值）给找到的最前边的位置
					arr[j] = temp;
				}
			}
		}
	}
}
